package practice13;

import java.util.HashMap;

/**
 * # 问题描述
 *
 * 输入一个长度为 4 倍数的字符串，只有`A`、`S`、`D`、`F`四个字母构成，现要求替换其中一个子串，调整为词频一样的字符串。例如`ADDF`，只需要替换`D`到`S`，就可以得到四个字母词频一样的字符串`ASDF`。求满足要求的最小子串长度。
 *
 * ## 输入格式
 *
 * 第一行输入一个字符串public class Main {
 *     public static String solution(int n) {
 *         // Please write your code here
 *         return "-2";
 *     }
 *
 *     public static void main(String[] args) {
 *         //  You can add more test cases here
 *         System.out.println(solution(2).equals("0.50000"));
 *         System.out.println(solution(931).equals("0.50054"));
 *         System.out.println(solution(924).equals("0.50000"));
 *         System.out.println(solution(545).equals("0.50092"));
 *     }
 * }
 *
 * ## 输出格式
 *
 * 输出 1 个整数，满足要求的最小子串长度
 *
 * ## 输入样例 1
 *
 * `ADDF`
 *
 * ## 输出样例 1
 *
 * `1`
 *
 * 样例说明：替换`D`为`S`，将`ADDF`转为`ASDF`
 *
 * ## 输入样例 2
 *
 * `ASAFASAFADDD`
 *
 * ## 输出样例 2
 *
 * 输出：`3`
 *
 * 样例说明：替换`AFA`为`SFF`，将`ASAFASAFADDD`转成`ASAFASSFFDDD`
 */
public class Main {
    public static int solution(String input) {
        // Please write your code here
        int n = input.length();
        int targetCount = n / 4; // 每个字符的目标出现次数

        // 统计每个字符的实际出现次数
        HashMap<Character, Integer> count = new HashMap<>();
        for (char c : input.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }

        // 记录超过目标次数的字符及其超出量
        HashMap<Character, Integer> excess = new HashMap<>();
        for (char c : new char[]{'A', 'S', 'D', 'F'}) {
            int diff = count.getOrDefault(c, 0) - targetCount;
            if (diff > 0) {
                excess.put(c, diff);
            }
        }

        // 如果没有字符超过目标次数，则整个字符串已经满足条件
        if (excess.isEmpty()) return 0;

        int left = 0, right = 0, minLen = n;

        while (right < n) {
            char rChar = input.charAt(right++);
            if (excess.containsKey(rChar)) {
                excess.put(rChar, excess.get(rChar) - 1);
                if (excess.get(rChar) == 0) {
                    excess.remove(rChar);
                }
            }

            // 当窗口外的所有字符都不再超过目标次数时，尝试收缩窗口
            while (excess.isEmpty()) {
                minLen = Math.min(minLen, right - left);
                char lChar = input.charAt(left++);
                if (count.containsKey(lChar)) {
                    count.put(lChar, count.get(lChar) - 1);
                    if (lChar == rChar) {
                        excess.put(rChar, 1);
                    }
                }
            }
        }

        return minLen;
        //return -2;
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        System.out.println(solution("ADDF") == 1);
        System.out.println(solution("ASAFASAFADDD") == 3);
    }
}